/*
 * =====================================================================================
 *
 *       Filename:  max-sum-seque.cpp
 *
 *    Description:  编程珠玑 第八章
 *
 *        Version:  1.0
 *        Created:  2011-11-16 10:05:27
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include <iostream>
#include <algorithm>
#include <iterator>

#include "UserTime.h"

int max_sum_seque1(int array[], int l, int r)
{
    int maxsofar = 0;
    for (int i = l; i <= r; ++i) {
        for (int j = i; j <= r; ++j) {

            int _max = 0;
            for (int k = i; k <= j; ++k) {
                _max += array[k];
            }
            maxsofar = (std::max)(maxsofar, _max);
        }
    }

    return maxsofar;
}

int max_sum_seque2(int array[], int l, int r)
{
    int maxsofar = 0;
    for (int i = l; i <= r; ++i) {
        int max = 0;
        for (int j = i; j <= r; ++j) {
            max += array[j];
            maxsofar = (std::max)(maxsofar, max);
        }
    }

    return maxsofar;
}

int max_sum_seque3(int array[], int l, int r)
{
    int n = r - l + 1;
    int *realarray = new int[n + 1];
    int *sumarray = realarray + 1;

    sumarray[l - 1] = 0;
    for (int i = l; i <= r; ++i) {
        sumarray[i] = sumarray[i - 1] + array[i];
    }

    int maxsofar = 0;
    for (int i = l; i <= r; ++i) {
        for (int j = i; j <= r; ++j) {
            int max = sumarray[j] - sumarray[i - 1];
            maxsofar = (std::max)(maxsofar, max);
        }
    }

    delete [] realarray;

    return maxsofar;
}

int max_sum_seque4(int array[], int l, int r)
{
    if (l > r) {
        return 0;
    }
    if (l == r) {
        return (std::max)(0, array[l]);
    }

    int m = l + (r - l) / 2;

    int sum = 0;
    int lmax = 0;
    for (int i = m; i >= l; --i) {
        sum += array[i];
        lmax = (std::max)(lmax, sum);
    }

    sum = 0;
    int rmax = 0;
    for (int i = m + 1; i <= r; ++i) {
        sum += array[i];
        rmax = (std::max)(rmax, sum);
    }

    int tmpmax = (std::max)(max_sum_seque4(array, l, m), max_sum_seque4(array, m + 1, r));
    return (std::max)(tmpmax, lmax + rmax);
}

int max_sum_seque5(int array[], int l, int r)
{
    int maxsofar = 0;
    int maxendsofar = 0;
    for (int i = l; i <= r; ++i) {
        maxendsofar = (std::max)(maxendsofar + array[i], 0);
        maxsofar = (std::max)(maxsofar, maxendsofar);
    }
    return maxsofar;
}

int main(int argc, char *argv[])
{
    srand(unsigned(time(NULL)));

    int tmp = 0;
    while (std::cin >> tmp) {
        int *array = new int[tmp];
        for (int i = 0; i < tmp; ++i) {
            array[i] = range_rand(-tmp, tmp);
        }

        CUserTime timer;
        timer.start();
        std::cout << "algorithm 1 : the max sum is " << max_sum_seque1(array, 0, tmp - 1) << std::endl;
        std::cout << "and the running time is " << timer.lapse() << std::endl;
        timer.start();
        std::cout << "algorithm 2 : the max sum is " << max_sum_seque2(array, 0, tmp - 1) << std::endl;
        std::cout << "and the running time is " << timer.lapse() << std::endl;
        timer.start();
        std::cout << "algorithm 3 : the max sum is " << max_sum_seque3(array, 0, tmp - 1) << std::endl;
        std::cout << "and the running time is " << timer.lapse() << std::endl;
        timer.start();
        std::cout << "algorithm 4 : the max sum is " << max_sum_seque4(array, 0, tmp - 1) << std::endl;
        std::cout << "and the running time is " << timer.lapse() << std::endl;
        timer.start();
        std::cout << "algorithm 5 : the max sum is " << max_sum_seque5(array, 0, tmp - 1) << std::endl;
        std::cout << "and the running time is " << timer.lapse() << std::endl;
        delete [] array;
    }
    return 0;
}
